// Vue 3 源码中的 LIS 算法
function getSequence(arr) {
  const p = arr.slice();        // 前驱节点数组
  console.log(p)
  const result = [0];           // 当前递增序列的索引
  const len = arr.length;
  
  for (let i = 0; i < len; i++) {
    const arrI = arr[i];
    console.log(arrI)
    if (arrI !== 0) {
      const j = result[result.length - 1];
      
      // 关键判断：当前元素是否大于序列最后一个元素
      if (arr[j] < arrI) {
        p[i] = j;
        result.push(i);
        continue;
      }
      
      // 二分查找找到合适的插入位置
      let u = 0, v = result.length - 1;
      while (u < v) {
        const c = (u + v) >> 1;
        if (arr[result[c]] < arrI) {
          u = c + 1;
        } else {
          v = c;
        }
      }
      
      // 替换策略，保持序列的最小末尾值
      if (arrI < arr[result[u]]) {
        if (u > 0) {
          p[i] = result[u - 1];
        }
        result[u] = i;
      }
    }
  }
  
  // 重构最终序列
  let u = result.length;
  let v = result[u - 1];
  while (u-- > 0) {
    result[u] = v;
    v = p[v];
  }
  
  return result;
}

const arr = '23223423423sadsassad333';
const result = getSequence(arr.split(''));
console.log(result);